package org.example.datastructure.ch9;

public class BTreeNode {
    public int val;
    public BTreeNode left, right;
    public BTreeNode(){
        val = -1;
        left = null;
        right = null;
    }
    public BTreeNode(int val){
        this.val = val;
        left = null;
        right = null;
    }
    public BTreeNode(int val, BTreeNode left, BTreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public BTreeNode find(int x,BTreeNode root){
        if(root == null) return null;
        if(root.val == x) return root;
        if(x<root.val) return find(x,root.left);
        else return find(x,root.right);
    }

    public void insert(int x,BTreeNode root){
        if(root==null){
            root = new BTreeNode(x);
        }
        if(x<root.val){
            insert(x,root.left);
        }
        else if(x>root.val){
            insert(x,root.right);
        }
    }
    public BTreeNode create(int[] nums){
        BTreeNode root = new BTreeNode(nums[0]);
        for(int num:nums){
            insert(num,root);
        }
        return root;
    }
    public void remove(int x,BTreeNode root){
        if(root==null) return;
        if(x<root.val) remove(x,root.left);
        else if(x>root.val) remove(x,root.right);
        else if(root.left!=null&right.right!=null){
            BTreeNode tmp = root.right;
            while(tmp.left!=null) tmp = tmp.left;
            root.val = tmp.val;
            remove(root.val,root.right);
        }
        else{
            root = root.left!=null?root.left:root.right;
        }
    }

}
